// @author: caoshi
// @date: 2021-08-28 20:31
package sort

/**
选择排序
实现思路是: 从0开始到倒数第2个元素, 将值最小的元素排到最前面(从小到大排)
依次循环直至排序完成
*/
func SelectionSort(srcArr []int) {
	length := len(srcArr)
	for i := 0; i < length-1; i++ {
		// 找到每轮循环中最小值的下标
		minIndex := i
		for j := i; j < length; j++ {
			if srcArr[j] < srcArr[minIndex] {
				minIndex = j
			}
		}

		// 将每轮循环的最小值移到最左边 (交换位置即可)
		// 常规方法交换数组元素
		//if minIndex != i {
		//	temp := resArr[minIndex]
		//	resArr[minIndex] = resArr[i]
		//	resArr[i] = temp
		//}

		// go 中特有的交换数组的方法
		srcArr[i], srcArr[minIndex] = srcArr[minIndex], srcArr[i]
	}

	//return srcArr
}

/**
冒泡排序
*/
func BubbleSort(srcArr []int) {
	length := len(srcArr)
	for i := 0; i < length-1; i++ {
		// 每一轮循环 如果左边的数大于右边的, 就交换两个数
		for j := 0; j < length-1-i; j++ {
			if srcArr[j] > srcArr[j+1] {
				srcArr[j], srcArr[j+1] = srcArr[j+1], srcArr[j]
			}
		}
	}
}

/**
快速排序
*/
func QuickSort(array []int, l int, r int) {
	if l >= r {
		return
	}
	left := l
	right := r
	// 选取基准值
	pivot := array[left]
	for left < right {
		for left < right && array[right] >= pivot {
			right--
		}
		if left < right {
			array[left] = array[right]
		}
		for left < right && array[left] <= pivot {
			left++
		}
		if left < right {
			array[right] = array[left]
		}
		if left >= right {
			array[left] = pivot
		}
	}
	QuickSort(array, l, right-1)
	QuickSort(array, right+1, r)

}
